package pers.lls.hds.heap;

import java.io.*;

/**
 * 堆的特点：
 * 1. 完全的二叉树
 * 2. 常用数组实现
 * 3. 每一个节点的关键字都大于/小于或等于子节点的关键字
 * 堆是一种树，主要用来实现优先级队列，由堆实现的优先级队列删除和插入的时间复杂度都为O(logN)
 * 堆排序对数据分布不敏感，与快速排序一样，时间复杂度都是O(N*logN)
 *
 * @author lilichai
 */
public class BasicHeap {

    class Node {
        private int iData;

        public Node(int key) {
            iData = key;
        }

        public int getKey() {
            return iData;
        }

        public void setKey(int id) {
            iData = id;
        }

    }

    private Node[] heapArray;
    private int maxSize;
    private int currentSize;

    public BasicHeap(int mx) {
        maxSize = mx;
        currentSize = 0;
        heapArray = new Node[maxSize];
    }

    public boolean insert(int key) {
        if (currentSize == maxSize) {
            return false;
        }
        Node newNode = new Node(key);
        heapArray[currentSize] = newNode;
        trickleUp(currentSize++);
        return true;
    }

    public void trickleUp(int currentSize) {
        int parent = (currentSize - 1) / 2;
        Node currentNode = heapArray[currentSize];
        while (currentSize > 0 && heapArray[parent].getKey() < currentNode.getKey()) {
            heapArray[currentSize] = heapArray[parent];
            currentSize = parent;
            parent = (parent - 1) / 2;
        }
        heapArray[currentSize] = currentNode;
    }

    public Node remove() {
        Node root = heapArray[0];
        heapArray[0] = heapArray[--currentSize];
        trickleDown(0);
        return root;
    }

    private void trickleDown(int index) {
        int largerChild;
        Node top = heapArray[index];
        while (index < currentSize / 2) {
            int leftChild = 2 * index + 1;
            int rightChild = leftChild + 1;
            if (rightChild < currentSize && heapArray[leftChild].getKey() < heapArray[rightChild].getKey()) {
                largerChild = rightChild;
            } else {
                largerChild = leftChild;
            }
            if (top.getKey() >= heapArray[largerChild].getKey()) {
                break;
            }
            heapArray[index] = heapArray[largerChild];
            index = largerChild;
        }
        heapArray[index] = top;
    }

    public boolean change(int index, int newValue) {
        if (index < 0 || index >= currentSize) {
            return false;
        }
        int oldValue = heapArray[index].getKey();
        heapArray[index].setKey(newValue);
        if (oldValue < newValue) {
            trickleUp(index);
        } else {
            trickleDown(index);
        }
        return true;
    }

    public boolean isEmpty() {
        return currentSize == 0;
    }

    public void displayHeap() {

        int nBlanks = 32;
        int itemsPerRow = 1;
        int column = 0;
        int j = 0;
        while (currentSize > 0) {
            if (column == 0) {
                for (int k = 0; k < nBlanks; k++) {
                    System.out.print(' ');
                }
            }
            System.out.print(heapArray[j].getKey());
            if (++j == currentSize) {
                break;
            }
            if (++column == itemsPerRow) {
                nBlanks /= 2;
                itemsPerRow *= 2;
                column = 0;
                System.out.println();
            } else {
                for (int k = 0; k < nBlanks * 2 - 2; k++) {
                    System.out.print(' ');
                }
            }
        }
        System.out.println();
    }

    public static void main(String[] args) throws IOException {
        BasicHeap theHeap = new BasicHeap(31);
        theHeap.insert(70);
        theHeap.insert(40);
        theHeap.insert(50);
        theHeap.insert(20);
        theHeap.insert(60);
        theHeap.insert(100);
        theHeap.insert(80);
        theHeap.insert(30);
        theHeap.insert(10);
        theHeap.insert(90);
        theHeap.displayHeap();
        for (int i = 0; i < 10; i++) {
            System.out.print(theHeap.remove().getKey() + " > ");
        }
    }
}